package basicSort.heapSort;

import java.util.*;

public class HeapSort {

    public static void heapSort(int[] arr){
        if( arr == null && arr.length < 2){
            return;
        }

        for(int i = arr.length - 1;i>=0;i--){
            heapfy(arr,i,arr.length-1);
        }

        int size = arr.length-1;

        while (size > 0){
            swap(arr,0,size);
            heapfy(arr,0 ,--size);
        }

        /*for(int i = 0 ; i < arr.length ; i++){
            System.out.print(arr[i] + " ");
        }*/

    }

    public static void heapfy(int[] arr , int i , int size){
        int left = i * 2 + 1;
        int right = left + 1;
        int large = 0;
        while (left <= size){
            if(left == size){
                large = left;
            }else {
                large = arr[left] >= arr[right] ? left : right;
            }
            if(arr[large]<=arr[i]){
                break;
            }
            swap(arr,i,large);
            i = large;
            left = i * 2 + 1;
            right = left+1;
        }

    }

    public static void swap(int[] arr , int i , int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int count = 100;

        int[] arr = new int[count];

        //为数组随机赋值
        for ( int i = 0 ; i < count ; i++){
            arr[i] =(int) (Math.random() * 100);
        }
        heapSort(arr);
        for(int i = 0 ; i < count ; i++){
            System.out.print(arr[i] + " ");
        }
    }

}
